1. Field of the Invention
The present invention relates to a method for determining a hop count, and more particularly, to a method for determining the maximum hop count in a bus having a tree structure.
2. Description of the Related Art
The IEEE-1394 for digital network interfaces is currently being standardized. The IEEE-1394 bus has a digital bus protocol for connecting personal computers and digital electric home equipment to each other. The IEEE-1394 bus protocol is widely applied to equipment such as digital video cameras (DVC), hard disc drives (HDD), printers, and personal computers (PC). Also, the IEEE-1394 bus protocol is being extended from a bus protocol for simply connecting peripheral equipment of computers, to a network protocol for performing data transmission among various systems such as PCs.
FIG. 1A is a block diagram showing an example of on IEEE-1394 bus having a tree structure. Referring to FIG. 1A, a plurality of apparatuses 100 through 108 which satisfy the IEEE-1394 standard are connected to the IEEE-1394 bus by 1394 cable. Here, the 1394 cable should not have loops. Namely, there should be only one 1394 cable path connecting one apparatus to another.
FIG. 1B illustrates the structure of ports connected to the IEEE-1394 bus. Referring to FIG. 1B, the apparatus connected to the IEEE-1394 bus includes ports (port0 through port2) to which the cable is connected. A node ID is designated to the apparatus. When an apparatus transmits data to, and receives data from, another apparatus, node IDs are used as the addresses of the concerned apparatuses. Node IDs are re-assigned whenever the bus is reset.
FIG. 2 schematically shows a protocol stack used in the IEEE-1394 standard. The protocol stack shown in FIG. 2 is necessary in order to operate the IEEE-1394 bus. Here, a physical layer 200 and a link layer 202 are realized as hardware in the form of an integrated circuit (IC) chip. A transaction layer 204 and a node manager 206 are realized as software.
The network connected by the IEEE-1394 bus is changed from a normal bus operation state to a bus reset state when a new apparatus is connected to the network through an arbitrary port on the network, or when a connected apparatus is removed from the network. Such a state transition is detected by the physical layer shown in FIG. 2. When a state transition is detected, a bus re-alignment process having the following sequence is performed.
In a bus reset state, a tree identification step is performed. In this step, it is sensed whether loops are formed in the connected state of a bus, and a root node for forming a tree is determined. Then, a self-identification step is performed. Each node determines the IEEE-1394 node ID thereof and broadcasts this to other nodes. Then, an isochronous manager determining step is performed to determine a node for managing an isochronous resource. Finally, a manager determining step is performed to determine a node for managing bus configuring information items. In this step, a topology map and a speed map are established and a gap count is optimized. The gap count is optimized by obtaining the maximum of the node to node hop counts for every possible combination of pairs of the bus in the topology map, obtaining the gap count using a table of the IEEE-1394 standard using the maximum value, and designating the gap count of the nodes using a physical layer configuring packet.
As mentioned above, the maximum hop count is used for extracting the gap count of the IEEE-1394 bus. The gap count is broadcast to the respective nodes by the physical layer configuring packet, thus determining the subaction gap of the bus as the optimal value. Therefore, the process of obtaining the maximum hop count is essential for effectively using the bandwidth of the 1394 bus. Such a gap count optimizing process is currently specified in the IEEE-1394 standard. However, methods of determining hop counts among all nodes and the maximum value among the hop counts are not specified in the IEEE-1394 standard at present. Therefore, for obtaining the maximum hop count, at present, the hop counts among all the nodes should be determined simply. There is a problem in that the amount of calculation is very large when many nodes are connected to the bus.
There is an algorithm for the shortest path of every possible combination of pairs or a method provided in the U.S. Pat. No. 5,687,319 by Cook, in another conventional method for solving this problem. According to the methods provided in the above references, the amount of calculation is reduced by some degree. However, the amount of calculation is still large since the calculation is performed in proportion to the square of the number of nodes.
To solve the above problem, it is an objective of the present invention to provide a method of quickly determining the maximum hop count.
Accordingly, to achieve the above objective, there is provided a method of determining the maximum hop count in a bus having a tree structure, comprising the steps of (a) obtaining hop counts with respect to all the child nodes of each node, obtaining hop counts with respect to all the possible combinations of node pairs in a sub tree in which each node is used as a root node, and obtaining the maximum value among the obtained hop counts as the first maximum value, (b) obtaining the sum of the upper two hop counts having the largest values among the hop counts to a leaf node in the sub tree, as the second maximum value, with respect to all the child nodes of each hop, and (c) determining a larger value between the first maximum value and the second maximum value as the maximum hop count, wherein the maximum value among the maximum hop count values of the respective nodes is determined as the maximum hop count of the bus tree by performing the steps (a) through (c) with respect to all the nodes.
To achieve the above objective, there is provided another method of determining the maximum hop count in a bus having a tree structure, comprising the steps of (a) configuring a first tree by setting an arbitrary node as a root node, (b) searching for the child node having the maximum length among the child nodes of the root node by scanning all the child nodes in the first tree, (c) configuring a second tree by setting the child node searched for in the step (b) as a new root node, (d) obtaining the maximum length by scanning all the child nodes in the second tree configured in the step (c), and (e) setting the maximum length obtained in the step (d) as the maximum hop count.